package leetcode;

import java.util.Arrays;

public class MinimumMovesEqualElements {

	//每次递增nums.length - 1个数 
	public int minMoves(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int n = nums.length;
        //数学问题：sum % n + n * Z = m * (n - 1)
        //Z属于自然数，求最小的m
        
        //思路错了，比如1、101，要相等不能这样子判断，只能说两个数相等时肯定是满足上式的
        //sum  + m * (n - 1)  = n * f, f为所有数都相等时的数字
        //然后再discuss中看到了新的讨论，原来还有一个条件
        //m + min = f; 最小的数始终加1
        //联立两式可得sum - m = n * min;
        //m = sum - n * min;
        int sum = 0, min = Integer.MAX_VALUE;
        for(int i : nums){
            sum += i;
            min = Math.min(min, i);
        }
        return sum - n * min;
    }
	
	//每次可以对1个数进行加1或者减1
    public int minMoves2(int[] nums) {
        //两个数如果最后变成相等, 移动的步数一定是a2 - a1
    	if(nums == null || nums.length <= 0){
    		return 0;
    	}
    	Arrays.sort(nums);
    	int length = nums.length;
    	int res = 0;
    	for(int i = 0; i < length / 2; i++){
    		res += nums[length - 1 - i] - nums[i];
    	}
    	return res;
    }
}
